#!/usr/bin/python3

def gcd(num_1,num_2):
    p,q=max(num_1,num_2),min(num_1,num_2)
    if q == 0:
        return p
    r = p%q
    return gcd(q,r)

s = int(input())
for x in range(1, s + 1):
    n, m = map(int, input().split())
    if n > m:
        greater = n
    else:
        greater = m
    while 1:
        if (greater % n == 0 and greater % m == 0):
            lcm = greater
            print(lcm)
            break
        greater += 1
    result = lcm / m
    print("Case #%d: %d" % (x, result))
